package QuestionDaily;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class countPairs_2824 {
    /**
     * @param nums 整数数组
     * @param target 整数 target
     * @return 返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。
     */
    public int countPairs(List<Integer> nums, int target) {
        /**
         * 想法是进行排序，相向双指针
         * 只关心这两个数的和是否小于 target，由于 a+b=b+a
         * 无论如何排列数组元素，都不会影响加法的结果，所以排序不影响答案。
         */
        Collections.sort(nums);
        int ans = 0, left = 0, right = nums.size() - 1;
        while (left < right) {
            if (nums.get(left) + nums.get(right) < target) {
                ans += right - left;
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }
    public int countPairs2(List<Integer> nums, int target) {
        /**
         * 暴力检索
         * 2ms
         */
        int count=0;
        for (int i=0;i<nums.size()-1;i++){
            int a=nums.get(i);
            for(int j=i+1;j<nums.size();j++){
                if(a+nums.get(j)<target)
                    count++;
            }
        }
        return count;
    }
}
